The present invention relates a method for simulating, planning and/or provisioning traffic flows in communication networks, particularly optical networks, more particularly optical networks employing wavelength division multiplexing (WDM).
Transport networks are typically wide area networks that provide connectivity for aggregated traffic streams. Modern transport networks increasingly employ optical technology, and particularly wavelength division multiplexing (WDM) technology, to utilize the vast transmission bandwidth of optical fiber. WDM is based on transmission of data over separate wavelength channels on each fiber. Presently, WDM is mainly employed as a point-to-point transmission technology. In such networks, optical signals on each wavelength are converted to electrical signals at each network node. On the other hand, a WDM optical networking technology, which has been developed within the last decade, and which is becoming commercially available, employs wavelengths on an end-to-end basis, without electrical conversion in the network.
Planning of a transport network refers to assigning network resources to a traffic demand. Efficient planning is essential in minimizing the investment made on the network required to accommodate a given demand. In WDM networks, traffic is carried by means of circuit switched connections, optically routed on the basis of their wavelength. In the context of WDM optical networks, planning means routing and wavelength selection for a set of end-to-end wavelength allocation demands (or “connection requests”), a demand distribution and a network structure being given.
A WDM network is characterized by its physical topology, that is, by the manner in which its nodes are interconnected by optical links. Though the ring is the most studied and most common topology today, mesh networks are being developed and deployed.
In a mesh optical network, a set of switching nodes is interconnected by a plurality of fiber links. It is assumed that each path p between any pair of source and destination nodes (not necessarily adjacent) requires a dedicated wavelength w on each link belonging to the path itself. The pair (p, w) is referred as “lightpath”, w being a vector collecting the wavelengths w used on each link of the path. If the path p connects adjacent nodes, the lightpath is typically referred as “lighthop”. A source-destination node pair may require more than one lightpath. The typical context assumes that there is a fixed set of wavelengths available on each fiber, and therefore the connections are established at the expense of possibly multiple fibers on network links, typically bundled in one or more optical cables. The switching nodes are the Optical Cross Connects (OXCs). They perform switching on the WDM transit lightpaths, preferably in all-optical way, that is, without intervention of electronics. In addition they may behave as terminal equipment for some lightpaths, performing add and/or drop functions. Further to switching, OXCs may effectuate wavelength conversion. Other nodes may perform exclusively add and/or drop functions (Optical Add/Drop Multiplexers, or OADMs). In the context of planning, the term “wavelength” may refer to a label assigned to a lightpath in each link, instead of the actual value of the wavelength itself. Each fiber has a cost, typically reflecting the installed fiber material, optical amplifiers, and optical termination equipment at both ends of the link. The cost of the OXCs and of the OADMs may also be taken into account. The objective of planning may be typically taken as the minimization of the total network cost.
In WDM networks, routing is coupled with wavelength assignment, that is, which wavelength channel should be allocated to a lightpath in each link. The combination of these two functions is called Routing and Wavelength Assignment (RWA). In the case of multifiber links, RWA becomes Routing, Fiber and Wavelength Assignment (RFWA), as also a particular fiber must be selected on each link for a given lightpath. The complexity of the RFWA function greatly depends on the wavelength conversion capability of the switching nodes of the network. WDM networks may be distinguished in three categories, according to their wavelength conversion capability:                a) Wavelength Path (WP) networks: no wavelength conversion capability is provided in the switching nodes;        b) Virtual Wavelength Path (VWP) networks: every node is fully equipped with wavelength converters so that an incoming optical channel can always be converted on an idle output wavelength;        c) Partial Virtual Wavelength Path (PVWP) networks: only part of the nodes are equipped with wavelength converters.        
Two different traffic types may be offered to a WDM network:                a) static traffic: a known set of permanent connection requests is assigned a priori to the network, which must be able to satisfy all the requests together, starting from the idle network;        b) dynamic traffic: connection requests arrive at random instants to the nodes of the network and connections are semi-permanent (i.e. temporary with long duration). Each connection is set up independently while other connections are active and network resources have already been allocated to other lightpaths. This situation is also referred in the art as “provisioning”. In general, with provisioning there is no warranty that the network is able to find enough idle resources to satisfy a particular connection request: in this case, the connection is blocked.        
Static traffic is usually considered when a new network should be started up or an existing infrastructure should undergo a large scale reconfiguration or a physical topology upgrading. In these cases the network can be planned according to future traffic. Static planning can be summarized as in the following: given a static traffic matrix, comprising a set of connection requests between pairs of source-destination nodes, find the optimum values of a set of network variables that minimize a given cost function, under a set of constraints. The choice of variables, cost function and constraints greatly varies from case to case.
Dynamic traffic can be considered during normal operation lifetime of the WDM network. In dynamic traffic conditions the optimal RFWA must be determined for every new lightpath requested in a given instant of time by a node pair of the network, keeping into account the network resources already allocated to other active connections. To perform the three functions of RFWA on the new connection request, a routing, a fiber and a wavelength assignment criterion has to be chosen: the main approach is to choose in a heuristic way among known simple algorithms. Path routing is usually done by “Shortest Path” (SP) or “Least Loaded Routing” (LLR). The SP method tends to route the new connection along the shortest physical path linking the source node to the destination node. For defining the distance two metrics can be used: the first, referred as “Minimum Hop” (mH), evaluates the number of links (or lighthops) concatenated to form the path; the second, referred “Minimum Length” (mL), considers the total physical length of the path. The LLR method tends to route the lightpath avoiding links with very high loads (i.e. a small number of free wavelengths).
Typical wavelength and fiber assignment criteria include “Pack”, “Spread”, “First Fit” and “Random”. “Pack” and “Spread” consider the utilization of wavelengths on the network and define a priority order, promoting the most and the least used wavelength in the network, respectively. “First Fit” creates an arbitrary and preset priority order for wavelength selection which is kept unchanged throughout the whole network. In “Random” criterion, no priority order is predetermined and the wavelength assignment is made randomly.
Solving the static traffic planning with heuristic algorithms developed for dynamic traffic is known. For example, G. Maier, A. Pattavina, L. Roberti, T. Chich, “Static-Lightpath Design by Heuristic Methods in Multifiber WDM Networks”, Proceedings of OptiComm 2000 SPIE Conf., Dallas, October 2000, pg. 64-75, disclose an approach to WDM multifiber network design and optimization under static traffic aimed to minimize the number of fibers in the network. The authors used a tool named “layered graph” (sometimes called wavelength graph) as a working auxiliary representation of the network state. This representation, often used for dynamic traffic analysis or for static optimization in mono-fiber networks, was used by the authors for a multifiber network optimization with static traffic.
The layered graph in a multifiber WDM network is built by replicating the physical network topology on a set of (W×F) parallel planes or graphs, where W is the number of wavelengths used in the network and F is the maximum number of fibers in a link: each of the n physical nodes of the network appears as a virtual image node in all the (W×F) planes. A further image of the node may represent its add-drop function. Vertical (bidirectional) arcs between the image nodes represent OXC switching operations (fiber switching and wavelength conversion). If a physical node is equipped with wavelength converters its corresponding virtual nodes in different W planes are joined by vertical arcs; otherwise only planes having the same wavelength are vertically connected. Associating a horizontal arc on the layered graph to a lighthop on the network implies both the adoption of the corresponding physical link of the topology and the choice of one particular fiber and one particular wavelength.
In the Maier et al. article mentioned above, a single algorithm performs all these operations exploiting the layered graph. Suitable weights are associated to the nodes, to the vertical arcs and to the horizontal arcs, so that the layered graph is transformed into a weighted graph. Then, a Dijkstra algorithm finds the connection path with the least total weight on the weighted graph, thus obtaining the RFWA of the lightpath.
A layered graph is also disclosed in A. Jukan and H. R. Van As, “Service-Specific Resource Allocation in WDM Networks with Quality Constraints”, IEEE Journal on Selected Areas in Communications, Vol. 18, No. 10, October 2000, pp. 2051-2061, that proposes a generic approach to service-differentiated connection accommodation in wavelength-routed networks where, for the network state representation, the supplementary network graphs are defined and referred to as service-specific wavelength-resource graphs. The graphs are used for the appropriate allocation of wavelengths on concatenated physical resources building a wavelength route, along which the necessary transmission quality is achieved and the required management and surveillance functions are provided.
A graph in which a technique usually referred to as “node splitting” is considered is disclosed in K.-C. Lee and V. O. K. Li, “A Wavelength-Convertible Optical Network”, IEEE Journal of Lightwave Technology, Vol. 11, No. 5/6, May/June 1993, pp. 962-970. At each node, each wavelength λ1 is connected to each wavelength λ2 on an inbound link I1 to each wavelength λ2 on an outbound link I2. If λ1≠λ2, a weight greater than zero is added. Furthermore, at each node, a super source vertex is created and connected to each wavelength on an outgoing link. Moreover, a super destination vertex is created and connected to each wavelength on an incoming link.
Y. Zhang, K. Taira, H. Takagi and S. K. Das, “An Efficient Heuristic for Routing and Wavelength Assignment in Optical WDM Networks”, Proceedings of IEEE ICC 2002, Vol. 5, April/May 2002, pp. 2734-2739, discloses a heuristic algorithm that sets up and releases lightpaths for connection requests dynamically. The authors disclose an auxiliary graph in which the nodes and the links in the original network are transformed to edges and vertices, respectively, and the availability of each wavelength on the input and output links of a node as well as the number of available wavelength converters are taken into account in determining the weights of edges.